#include "xtypes.h"

template <class T1, class T2>
struct def_binary_search_compare
{
	inline int operator()( const T1 & v1, const T2 & v2 ){
		if( v1 == v2 )return 0;
		if( v1 > v2 )return 1;
		return -1;
	}
};

template <class T1, class T2, typename cmpT = def_binary_search_compare<T1, T2> >
struct xbinary_search
{
	static inline int search_insertpoint( const T1 * pTArray, int nArraySize, const T2 & v )
	{
		int insertpoint;
		_search( pTArray, nArraySize, v, insertpoint );
		return insertpoint;
	}

	static inline int search_value( const T1 * pTArray, int nArraySize, const T2 & v )
	{
		int insertpoint;
		return _search( pTArray, nArraySize, v, insertpoint );
	}
private:
	static typename cmpT _cmp;
	static inline int _search( const T1 * pTArray, int nArraySize, const T2 & v, int & insertpoint )
	{
		int s = 0, e = nArraySize, m, ret;

		while( s < e )
		{
			m = (s+e)/2;
			ret = _cmp( pTArray[m], v );
			if( ret == 0 )
			{
				insertpoint = m;
				return m;
			}

			if( ret > 0 )
				e = m;
			else
			{
				if( s == m )
					break;
				s = m+1;
			}
		}
		insertpoint = e;
		return -1;
	}
};

template <class T1, class T2, typename cmpT>
typename cmpT xbinary_search<T1,T2,cmpT>::_cmp;